import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;

/**
 * @author tim
 */
public class MoveToFront {

    // apply move-to-front encoding, reading from standard input and writing to standard output
    public static void encode() {
        Node head = initSequence();
        while (!BinaryStdIn.isEmpty()) {
            char c = BinaryStdIn.readChar();
            int index = compress(c, head);
            BinaryStdOut.write(index, 8);
        }
        BinaryStdOut.close();
    }

    // apply move-to-front decoding, reading from standard input and writing to standard output
    public static void decode() {
        Node head = initSequence();
        while (!BinaryStdIn.isEmpty()) {
            char c = BinaryStdIn.readChar(8);
            char ch = expand(c, head);
            // System.out.println(index);
            // System.out.println(head.next);
            BinaryStdOut.write(ch);
        }
        BinaryStdOut.close();
    }

    private static Node initSequence() {
        char c = '\u0000';
        Node head = new Node(c);
        Node node = head;
        for (int i = 0; i < 256; i++) {
            node.next = new Node(c++);
            node = node.next;
        }
        return head;
    }

    private static int compress(char c, Node head) {
        Node node = head.next;
        Node pre = head;
        int index = 0;
        while (node != null && node.ch != c) {
            pre = node;
            node = node.next;
            index++;
        }
        if (node != null) {
            pre.next = node.next;
            node.next = head.next;
            head.next = node;
        }
        return index;
    }

    private static char expand(char index, Node head) {
        Node node = head.next;
        Node pre = head;
        for (int i = 0; i < index; i++) {
            pre = node;
            node = node.next;
        }

        if (node != null) {
            pre.next = node.next;
            node.next = head.next;
            head.next = node;
        }
        return node.ch;
    }

    private static class Node {
        private final char ch;
        private Node next;

        Node(char c) {
            ch = c;
        }

        public String toString() {
            Node node = this;
            String s = "";
            while (node != null) {
                s += "，" + node.ch;
                node = node.next;
            }
            return s;
        }
    }

    // if args[0] is "-", apply move-to-front encoding
    // if args[0] is "+", apply move-to-front decoding
    public static void main(String[] args) {
        if (args[0].equals("-")) {
            encode();
        } else {
            if (!args[0].equals("+")) {
                throw new IllegalArgumentException("Illegal command line argument");
            }
            decode();
        }
    }
}
